/**
 * @author tmh
 * @date 2024/10/17 11:53
 * @description
 */
public class T31下一个排列2 {
    public void nextPermutation(int[] nums) {
        boolean flag = false;
        int index = 0;
        for (int i = nums.length-1; i >= 1; i--) {
            if (nums[i - 1] < nums[i]) {
                flag = true;
                index = i - 1;
                break;
            }
        }
        if (!flag) {
            swap(nums, 0, nums.length - 1);
        } else {
            //找到第一个大于nums[index]的数字，因为index后面的数都是降序的，所有交换后的数也是降序的
            for (int i = nums.length - 1; i >= 0; i--) {
                if (nums[i] > nums[index]) {
                    int temp = nums[i];
                    nums[i] = nums[index];
                    nums[index] = temp;
                    break;
                }
            }
            swap(nums, index + 1, nums.length - 1);
        }
    }

    private void swap(int[] nums, int left, int right) {
        for (int i = left, j = right; i < j; i++, j--) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
